<?xml version='1.0' encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html lang="en" xml:lang="en" xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <link href="cpip.css" rel="stylesheet" type="text/css" />
    <title>File: /Users/paulross/dev/linux/linux-3.13/include/linux/list_lru.h</title>
  </head>
  <body>
    <h1>File: /Users/paulross/dev/linux/linux-3.13/include/linux/list_lru.h</h1>
    <p>Green shading in the line number column
means the source is part of the translation unit, red means it is conditionally excluded.
Highlighted line numbers link to the translation unit page. Highlighted macros link to
the macro page.</p>
    <pre><a name="1" /><span class="True">       1:</span> <span class="k">/*</span>
<a name="2" /><span class="True">       2:</span> <span class="k"> * Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved.</span>
<a name="3" /><span class="True">       3:</span> <span class="k"> * Authors: David Chinner and Glauber Costa</span>
<a name="4" /><span class="True">       4:</span> <span class="k"> *</span>
<a name="5" /><span class="True">       5:</span> <span class="k"> * Generic LRU infrastructure</span>
<a name="6" /><span class="True">       6:</span> <span class="k"> */</span>
<a name="7" /><span class="True">       7:</span> <span class="f">#</span><span class="n">ifndef</span> <a href="cpu.c_macros_noref.html#_X0xSVV9MSVNUX0hfMA__"><span class="b">_LRU_LIST_H</span></a>
<a name="8" /><span class="True">       8:</span> <span class="f">#</span><span class="n">define</span> <a href="cpu.c_macros_noref.html#_X0xSVV9MSVNUX0hfMA__"><span class="b">_LRU_LIST_H</span></a>
<a name="9" /><span class="True">       9:</span> 
<a name="10" /><span class="True">      10:</span> <span class="f">#</span><span class="n">include</span> <span class="f">&lt;</span><span class="b">linux</span><span class="f">/</span><span class="b">list</span><span class="f">.</span><span class="b">h</span><span class="f">&gt;</span>
<a name="11" /><span class="True">      11:</span> <span class="f">#</span><span class="n">include</span> <span class="f">&lt;</span><span class="b">linux</span><span class="f">/</span><span class="b">nodemask</span><span class="f">.</span><span class="b">h</span><span class="f">&gt;</span>
<a name="12" /><span class="True">      12:</span> 
<a name="13" /><span class="True">      13:</span> <span class="k">/* list_lru_walk_cb has to always return one of those */</span>
<a name="14" /><span class="True">      14:</span> <span class="m">enum</span> <span class="b">lru_status</span> <span class="f">{</span>
<a name="15" /><span class="True">      15:</span>     <span class="b">LRU_REMOVED</span><span class="f">,</span>        <span class="k">/* item removed from list */</span>
<a name="16" /><span class="True">      16:</span>     <span class="b">LRU_ROTATE</span><span class="f">,</span>        <span class="k">/* item referenced, give another pass */</span>
<a name="17" /><span class="True">      17:</span>     <span class="b">LRU_SKIP</span><span class="f">,</span>        <span class="k">/* item cannot be locked, skip */</span>
<a name="18" /><span class="True">      18:</span>     <span class="b">LRU_RETRY</span><span class="f">,</span>        <span class="k">/* item not freeable. May drop the lock</span>
<a name="19" /><span class="True">      19:</span> <span class="k">                   internally, but has to return locked. */</span>
<a name="20" /><span class="True">      20:</span> <span class="f">}</span><span class="f">;</span>
<a name="21" /><span class="True">      21:</span> 
<a name="22" /><span class="True">      22:</span> <span class="m">struct</span> <span class="b">list_lru_node</span> <span class="f">{</span>
<a name="23" /><span class="True">      23:</span>     <span class="b">spinlock_t</span>        <span class="b">lock</span><span class="f">;</span>
<a name="24" /><span class="True">      24:</span>     <span class="m">struct</span> <span class="b">list_head</span>    <span class="b">list</span><span class="f">;</span>
<a name="25" /><span class="True">      25:</span>     <span class="k">/* kept as signed so we can catch imbalance bugs */</span>
<a name="26" /><span class="True">      26:</span>     <span class="m">long</span>            <span class="b">nr_items</span><span class="f">;</span>
<a name="27" /><span class="True">      27:</span> <span class="f">}</span> <a href="cpu.c_macros_ref.html#_X19fX2NhY2hlbGluZV9hbGlnbmVkX2luX3NtcF8w"><span class="b">____cacheline_aligned_in_smp</span></a><span class="f">;</span>
<a name="28" /><span class="True">      28:</span> 
<a name="29" /><span class="True">      29:</span> <span class="m">struct</span> <span class="b">list_lru</span> <span class="f">{</span>
<a name="30" /><span class="True">      30:</span>     <span class="m">struct</span> <span class="b">list_lru_node</span>    <span class="f">*</span><span class="b">node</span><span class="f">;</span>
<a name="31" /><span class="True">      31:</span>     <span class="b">nodemask_t</span>        <span class="b">active_nodes</span><span class="f">;</span>
<a name="32" /><span class="True">      32:</span> <span class="f">}</span><span class="f">;</span>
<a name="33" /><span class="True">      33:</span> 
<a name="34" /><span class="True">      34:</span> <span class="m">void</span> <span class="b">list_lru_destroy</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_lru</span> <span class="f">*</span><span class="b">lru</span><span class="f">)</span><span class="f">;</span>
<a name="35" /><span class="True">      35:</span> <span class="m">int</span> <span class="b">list_lru_init</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_lru</span> <span class="f">*</span><span class="b">lru</span><span class="f">)</span><span class="f">;</span>
<a name="36" /><span class="True">      36:</span> 
<a name="37" /><span class="True">      37:</span> <span class="k">/**</span>
<a name="38" /><span class="True">      38:</span> <span class="k"> * list_lru_add: add an element to the lru list&apos;s tail</span>
<a name="39" /><span class="True">      39:</span> <span class="k"> * @list_lru: the lru pointer</span>
<a name="40" /><span class="True">      40:</span> <span class="k"> * @item: the item to be added.</span>
<a name="41" /><span class="True">      41:</span> <span class="k"> *</span>
<a name="42" /><span class="True">      42:</span> <span class="k"> * If the element is already part of a list, this function returns doing</span>
<a name="43" /><span class="True">      43:</span> <span class="k"> * nothing. Therefore the caller does not need to keep state about whether or</span>
<a name="44" /><span class="True">      44:</span> <span class="k"> * not the element already belongs in the list and is allowed to lazy update</span>
<a name="45" /><span class="True">      45:</span> <span class="k"> * it. Note however that this is valid for *a* list, not *this* list. If</span>
<a name="46" /><span class="True">      46:</span> <span class="k"> * the caller organize itself in a way that elements can be in more than</span>
<a name="47" /><span class="True">      47:</span> <span class="k"> * one type of list, it is up to the caller to fully remove the item from</span>
<a name="48" /><span class="True">      48:</span> <span class="k"> * the previous list (with list_lru_del() for instance) before moving it</span>
<a name="49" /><span class="True">      49:</span> <span class="k"> * to @list_lru</span>
<a name="50" /><span class="True">      50:</span> <span class="k"> *</span>
<a name="51" /><span class="True">      51:</span> <span class="k"> * Return value: true if the list was updated, false otherwise</span>
<a name="52" /><span class="True">      52:</span> <span class="k"> */</span>
<a name="53" /><span class="True">      53:</span> <span class="m">bool</span> <span class="b">list_lru_add</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_lru</span> <span class="f">*</span><span class="b">lru</span><span class="f">,</span> <span class="m">struct</span> <span class="b">list_head</span> <span class="f">*</span><span class="b">item</span><span class="f">)</span><span class="f">;</span>
<a name="54" /><span class="True">      54:</span> 
<a name="55" /><span class="True">      55:</span> <span class="k">/**</span>
<a name="56" /><span class="True">      56:</span> <span class="k"> * list_lru_del: delete an element to the lru list</span>
<a name="57" /><span class="True">      57:</span> <span class="k"> * @list_lru: the lru pointer</span>
<a name="58" /><span class="True">      58:</span> <span class="k"> * @item: the item to be deleted.</span>
<a name="59" /><span class="True">      59:</span> <span class="k"> *</span>
<a name="60" /><span class="True">      60:</span> <span class="k"> * This function works analogously as list_lru_add in terms of list</span>
<a name="61" /><span class="True">      61:</span> <span class="k"> * manipulation. The comments about an element already pertaining to</span>
<a name="62" /><span class="True">      62:</span> <span class="k"> * a list are also valid for list_lru_del.</span>
<a name="63" /><span class="True">      63:</span> <span class="k"> *</span>
<a name="64" /><span class="True">      64:</span> <span class="k"> * Return value: true if the list was updated, false otherwise</span>
<a name="65" /><span class="True">      65:</span> <span class="k"> */</span>
<a name="66" /><span class="True">      66:</span> <span class="m">bool</span> <span class="b">list_lru_del</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_lru</span> <span class="f">*</span><span class="b">lru</span><span class="f">,</span> <span class="m">struct</span> <span class="b">list_head</span> <span class="f">*</span><span class="b">item</span><span class="f">)</span><span class="f">;</span>
<a name="67" /><span class="True">      67:</span> 
<a name="68" /><span class="True">      68:</span> <span class="k">/**</span>
<a name="69" /><span class="True">      69:</span> <span class="k"> * list_lru_count_node: return the number of objects currently held by @lru</span>
<a name="70" /><span class="True">      70:</span> <span class="k"> * @lru: the lru pointer.</span>
<a name="71" /><span class="True">      71:</span> <span class="k"> * @nid: the node id to count from.</span>
<a name="72" /><span class="True">      72:</span> <span class="k"> *</span>
<a name="73" /><span class="True">      73:</span> <span class="k"> * Always return a non-negative number, 0 for empty lists. There is no</span>
<a name="74" /><span class="True">      74:</span> <span class="k"> * guarantee that the list is not updated while the count is being computed.</span>
<a name="75" /><span class="True">      75:</span> <span class="k"> * Callers that want such a guarantee need to provide an outer lock.</span>
<a name="76" /><span class="True">      76:</span> <span class="k"> */</span>
<a name="77" /><span class="True">      77:</span> <span class="m">unsigned</span> <span class="m">long</span> <span class="b">list_lru_count_node</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_lru</span> <span class="f">*</span><span class="b">lru</span><span class="f">,</span> <span class="m">int</span> <span class="b">nid</span><span class="f">)</span><span class="f">;</span>
<a name="78" /><span class="True">      78:</span> <span class="m">static</span> <span class="m">inline</span> <span class="m">unsigned</span> <span class="m">long</span> <span class="b">list_lru_count</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_lru</span> <span class="f">*</span><span class="b">lru</span><span class="f">)</span>
<a name="79" /><span class="True">      79:</span> <span class="f">{</span>
<a name="80" /><span class="True">      80:</span>     <span class="m">long</span> <span class="b">count</span> <span class="f">=</span> <span class="c">0</span><span class="f">;</span>
<a name="81" /><span class="True">      81:</span>     <span class="m">int</span> <span class="b">nid</span><span class="f">;</span>
<a name="82" /><span class="True">      82:</span> 
<a name="83" /><span class="True">      83:</span>     <a href="cpu.c_macros_ref.html#_Zm9yX2VhY2hfbm9kZV9tYXNrXzA_"><span class="b">for_each_node_mask</span></a><span class="f">(</span><span class="b">nid</span><span class="f">,</span> <span class="b">lru</span><span class="f">-&gt;</span><span class="b">active_nodes</span><span class="f">)</span>
<a name="84" /><span class="True">      84:</span>         <span class="b">count</span> <span class="f">+=</span> <span class="b">list_lru_count_node</span><span class="f">(</span><span class="b">lru</span><span class="f">,</span> <span class="b">nid</span><span class="f">)</span><span class="f">;</span>
<a name="85" /><span class="True">      85:</span> 
<a name="86" /><span class="True">      86:</span>     <span class="m">return</span> <span class="b">count</span><span class="f">;</span>
<a name="87" /><span class="True">      87:</span> <span class="f">}</span>
<a name="88" /><span class="True">      88:</span> 
<a name="89" /><span class="True">      89:</span> <span class="m">typedef</span> <span class="m">enum</span> <span class="b">lru_status</span>
<a name="90" /><span class="True">      90:</span> <span class="f">(</span><span class="f">*</span><span class="b">list_lru_walk_cb</span><span class="f">)</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_head</span> <span class="f">*</span><span class="b">item</span><span class="f">,</span> <span class="b">spinlock_t</span> <span class="f">*</span><span class="b">lock</span><span class="f">,</span> <span class="m">void</span> <span class="f">*</span><span class="b">cb_arg</span><span class="f">)</span><span class="f">;</span>
<a name="91" /><span class="True">      91:</span> <span class="k">/**</span>
<a name="92" /><span class="True">      92:</span> <span class="k"> * list_lru_walk_node: walk a list_lru, isolating and disposing freeable items.</span>
<a name="93" /><span class="True">      93:</span> <span class="k"> * @lru: the lru pointer.</span>
<a name="94" /><span class="True">      94:</span> <span class="k"> * @nid: the node id to scan from.</span>
<a name="95" /><span class="True">      95:</span> <span class="k"> * @isolate: callback function that is resposible for deciding what to do with</span>
<a name="96" /><span class="True">      96:</span> <span class="k"> *  the item currently being scanned</span>
<a name="97" /><span class="True">      97:</span> <span class="k"> * @cb_arg: opaque type that will be passed to @isolate</span>
<a name="98" /><span class="True">      98:</span> <span class="k"> * @nr_to_walk: how many items to scan.</span>
<a name="99" /><span class="True">      99:</span> <span class="k"> *</span>
<a name="100" /><span class="True">     100:</span> <span class="k"> * This function will scan all elements in a particular list_lru, calling the</span>
<a name="101" /><span class="True">     101:</span> <span class="k"> * @isolate callback for each of those items, along with the current list</span>
<a name="102" /><span class="True">     102:</span> <span class="k"> * spinlock and a caller-provided opaque. The @isolate callback can choose to</span>
<a name="103" /><span class="True">     103:</span> <span class="k"> * drop the lock internally, but *must* return with the lock held. The callback</span>
<a name="104" /><span class="True">     104:</span> <span class="k"> * will return an enum lru_status telling the list_lru infrastructure what to</span>
<a name="105" /><span class="True">     105:</span> <span class="k"> * do with the object being scanned.</span>
<a name="106" /><span class="True">     106:</span> <span class="k"> *</span>
<a name="107" /><span class="True">     107:</span> <span class="k"> * Please note that nr_to_walk does not mean how many objects will be freed,</span>
<a name="108" /><span class="True">     108:</span> <span class="k"> * just how many objects will be scanned.</span>
<a name="109" /><span class="True">     109:</span> <span class="k"> *</span>
<a name="110" /><span class="True">     110:</span> <span class="k"> * Return value: the number of objects effectively removed from the LRU.</span>
<a name="111" /><span class="True">     111:</span> <span class="k"> */</span>
<a name="112" /><span class="True">     112:</span> <span class="m">unsigned</span> <span class="m">long</span> <span class="b">list_lru_walk_node</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_lru</span> <span class="f">*</span><span class="b">lru</span><span class="f">,</span> <span class="m">int</span> <span class="b">nid</span><span class="f">,</span>
<a name="113" /><span class="True">     113:</span>                  <span class="b">list_lru_walk_cb</span> <span class="b">isolate</span><span class="f">,</span> <span class="m">void</span> <span class="f">*</span><span class="b">cb_arg</span><span class="f">,</span>
<a name="114" /><span class="True">     114:</span>                  <span class="m">unsigned</span> <span class="m">long</span> <span class="f">*</span><span class="b">nr_to_walk</span><span class="f">)</span><span class="f">;</span>
<a name="115" /><span class="True">     115:</span> 
<a name="116" /><span class="True">     116:</span> <span class="m">static</span> <span class="m">inline</span> <span class="m">unsigned</span> <span class="m">long</span>
<a name="117" /><span class="True">     117:</span> <span class="b">list_lru_walk</span><span class="f">(</span><span class="m">struct</span> <span class="b">list_lru</span> <span class="f">*</span><span class="b">lru</span><span class="f">,</span> <span class="b">list_lru_walk_cb</span> <span class="b">isolate</span><span class="f">,</span>
<a name="118" /><span class="True">     118:</span>           <span class="m">void</span> <span class="f">*</span><span class="b">cb_arg</span><span class="f">,</span> <span class="m">unsigned</span> <span class="m">long</span> <span class="b">nr_to_walk</span><span class="f">)</span>
<a name="119" /><span class="True">     119:</span> <span class="f">{</span>
<a name="120" /><span class="True">     120:</span>     <span class="m">long</span> <span class="b">isolated</span> <span class="f">=</span> <span class="c">0</span><span class="f">;</span>
<a name="121" /><span class="True">     121:</span>     <span class="m">int</span> <span class="b">nid</span><span class="f">;</span>
<a name="122" /><span class="True">     122:</span> 
<a name="123" /><span class="True">     123:</span>     <a href="cpu.c_macros_ref.html#_Zm9yX2VhY2hfbm9kZV9tYXNrXzA_"><span class="b">for_each_node_mask</span></a><span class="f">(</span><span class="b">nid</span><span class="f">,</span> <span class="b">lru</span><span class="f">-&gt;</span><span class="b">active_nodes</span><span class="f">)</span> <span class="f">{</span>
<a name="124" /><span class="True">     124:</span>         <span class="b">isolated</span> <span class="f">+=</span> <span class="b">list_lru_walk_node</span><span class="f">(</span><span class="b">lru</span><span class="f">,</span> <span class="b">nid</span><span class="f">,</span> <span class="b">isolate</span><span class="f">,</span>
<a name="125" /><span class="True">     125:</span>                            <span class="b">cb_arg</span><span class="f">,</span> <span class="f">&amp;</span><span class="b">nr_to_walk</span><span class="f">)</span><span class="f">;</span>
<a name="126" /><span class="True">     126:</span>         <span class="m">if</span> <span class="f">(</span><span class="b">nr_to_walk</span> <span class="f">&lt;=</span> <span class="c">0</span><span class="f">)</span>
<a name="127" /><span class="True">     127:</span>             <span class="m">break</span><span class="f">;</span>
<a name="128" /><span class="True">     128:</span>     <span class="f">}</span>
<a name="129" /><span class="True">     129:</span>     <span class="m">return</span> <span class="b">isolated</span><span class="f">;</span>
<a name="130" /><span class="True">     130:</span> <span class="f">}</span>
<a name="131" /><span class="True">     131:</span> <span class="f">#</span><span class="n">endif</span> <span class="k">/* _LRU_LIST_H */</span>
<a name="132" /><span class="True">     132:</span> </pre>
  </body>
</html>
